package com.algorithm;

import java.util.Arrays;

/**
 * @program: study
 * @className: CoinCharge
 * @description: TODO
 * @author: kukuxiahuni
 * @create: 2019-09-16 11:33
 * @version: v1.0
 **/
public class CoinCharge {

    public static void main(String[] args) {

        CoinCharge coinCharge = new CoinCharge();
        int[] coins = {1, 2, 5};
        System.out.println(coinCharge.coinCharge(coins, 11));
        System.out.println(coinCharge.coinChargeWithMemo(coins, 11));

    }

    /**
     * @return:
     * @auther: kukuxiahuni
     * @date: 2019-09-16 11:34
     * @modify_auther: kukuxiahuni
     * @modify_time: 2019-09-16 11:34
     **/
    int coinCharge(int[] coins, int amount) {

        if (amount == 0) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;

        for (int coin : coins) {
            //1. 结果不可达
            if (amount - coin < 0) {
                continue;
            }

            int subCoin = coinCharge(coins, amount - coin);
            //子问题无解
            if (subCoin == -1) {
                continue;
            }
            ans = Math.min(ans, subCoin + 1);
        }
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }

    int coinChargeWithMemo(int[] coins, int amount) {
        int[] memo = new int[amount + 1];
        return helper(coins, amount, memo);
    }

    int helper(int[] coins, int amount, int[] memo) {

        if (amount == 0) {
            return 0;
        }

        int ans = Integer.MAX_VALUE;

        for (int coin : coins) {
            if (amount - coin < 0) {
                continue;
            }

            int sub = helper(coins, amount - coin, memo);
            if (sub == -1) {
                continue;
            }

            ans = Math.min(ans, sub + 1);
        }

        memo[amount] = (ans == Integer.MAX_VALUE) ? -1 : ans;
        return memo[amount];
    }

    /**
     * 功能描述: dp，动态规划问题
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2019-09-16 19:36
     * @modify_auther: kukuxiahuni
     * @modify_time: 2019-09-16 19:36
     **/
    int coinChargeWithDp(int[] coins, int amount) {

        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);

        for (int i = 0; i <= amount; ++i) {
            for (int coin : coins) {
                if (i - coin < 0) {
                    continue;
                }

                dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
            }
        }
        return (dp[amount] == amount + 1) ? -1 : dp[amount];


    }


}
